﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//
//long Fib(int n)
//{
//	if (n < 3)
//		return 1;
//	return Fib(n - 1) + Fib(n - 2);
//}
//int main()
//{
//	int i = 40;
//	int ret = Fib(i);
//	printf("%d\n", ret);
//	return 0;
//}
//void Func1(int N)
//{
//    int count = 0;
//    for (int i = 0; i < N; ++i)
//    {
//        for (int j = 0; j < N; ++j)
//        {
//            ++count;
//        }
//    }
//
//    for (int k = 0; k < 2 * N; ++k)
//    {
//        ++count;
//    }
//
//    int M = 10;
//    while (M--)
//    {
//        ++count;
//    }
//    printf("%d\n", count);
//}
//基本操作执行了F(N)=N^2+2*N+10，因此时间复杂度就时O(N^2)

//void Func2(int N)
//{
//    int count = 0;
//    for (int k = 0; k < 2 * N; ++k)
//    {
//        ++count;
//    }
//
//    int M = 10;
//    while (M--)
//    {
//        ++count;
//    }
//
//    printf("%d\n", count);
//}
//基本操作执行了2N+10次，因此时间复杂度为 O(N)

//void Func3(int N, int M)
//{
//    int count = 0;
//    for (int k = 0; k < M; ++k)
//    {
//        ++count;
//    }
//
//    for (int k = 0; k < N; ++k)
//    {
//        ++count;
//    }
//    printf("%d\n", count);
//}
//基本操作执行了M+N次，有两个未知数M和N，时间复杂度为 O(N+M)

//void Func4(int N)
//{
//    int count = 0;
//    for (int k = 0; k < 100; ++k)
//    {
//        ++count;
//    }
//    printf("%d\n", count);
//}
//基本操作执行了100次，时间复杂度为 O(1)

//void BubbleSort(int* a, int n)
//{
//    assert(a);
//    for (size_t end = n; end > 0; --end)
//    {
//        int exchange = 0;
//        for (size_t i = 1; i < end; ++i)
//        {
//            if (a[i - 1] > a[i])
//            {
//                Swap(&a[i - 1], &a[i]);
//                exchange = 1;
//            }
//        }
//
//        if (exchange == 0)
//            break;
//    }
//}
//总共的次数就是1+2+3+...+n-2+n-1=(N*(N+1)/2次，所以时间复杂度是O(N^2)
//int BinarySearch(int* a, int n, int x)
//{
//    assert(a);
//    int begin = 0;
//    int end = n - 1;
//    // [begin, end]：begin和end是左闭右闭区间，因此有=号
//    while (begin <= end)
//    {
//        int mid = begin + ((end - begin) >> 1);
//        if (a[mid] < x)
//            begin = mid + 1;
//        else if (a[mid] > x)
//            end = mid - 1;
//        else
//            return mid;
//    }
//    return -1;
//}

//long long Fac(size_t N)
//{
//    if (0 == N)
//        return 1;
//
//    return Fac(N - 1) * N;
//}
//通过递归实现1*2*3*...*(n-1)*n ，也就是说一共递归了n次，所以时间复杂度就是O(n)

//long long Fib(size_t N)
//{
//    if (N < 3)
//        return 1;
//
//    return Fib(N - 1) + Fib(N - 2);
//}

//long long* Fibonacci(size_t n)
//{
//    if (n == 0)
//        return NULL;
//    long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
//    fibArray[0] = 0;
//    fibArray[1] = 1;
//    for (int i = 2; i <= n; ++i)
//    {
//        fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
//    }
//    return fibArray;
//}
//// 计算阶乘递归Fac的空间复杂度？
//long long Fac(size_t N)
//{
//    if (N == 0)
//        return 1;
//    return Fac(N - 1) * N;
//}

int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{
    int i = 0;
    int z = numsSize / sizeof(nums[0]);
    for (i = 0; i < z; i++)
    {
        for (int j = i + 1; j < z; j++)
        {
            if (nums[i] + nums[j] == target)
            {
                int* sz = (int*)malloc(2 * sizeof(int));
                sz[0] = i;
                sz[1] = j;
                return sz;
            }
        }
    }
    return NULL;
}
